Матч 311, Просуммировать всех (SumThemAll)

Дивизион 1, Уровень 2

Найти сумму цифр всех чисел от lowerBound до upperBound.

Класс: SumThemAll

Метод: long long getSum(int lowerBound, int upperBound)

Ограничения: 0 £ upperBound £ 2*10⁹, 0 £ lowerBound £ upperBound.

Вход. Два целых числа lowerBound и upperBound.

Выход. Сумма цифр всех чисел от lowerBound до upperBound.

Пример входа

lowerBound	upperBound
0	3
14	53
24660	308357171

Пример выхода

6

296

11379854844

РЕШЕНИЕ

динамическое программирование

Пусть функция f(x) вычисляет сумму цифр всех чисел от 0 до x. Тогда ответом задачи будет значение f(upperBound) – f(lowerBound – 1).

Заведем массив dp[10][11], в котором dp[i][j] равно сумме цифр всех j - значных чисел, первая цифра которых равна i. Изначально положим dp[i][0] = 0. Ячейка dp[0][j] содержит сумму цифр всех чисел, содержащих менее j цифр, то есть сумму цифр всех (j – 1) - значных чисел, начинающихся с любой цифры включая ноль:

dp[0][j] =

Любое j - значное число, первая цифра которого равна i, образуется из (j – 1) - значного числа приписыванием впереди цифры i. Поэтому сумма их цифр равна сумме цифр (j – 1) - значных чисел плюс цифра i, умноженная на количество j - значных чисел с первой цифрой i (количество последних равно 10^j-1). Получаем соотношение:

dp[i][j] = dp[0][j] + 10^j-1 * i

Остается описать вычисление функции f(x). Очевидно, что f(0) = 0. Пусть x = . Для вычисления f(x) разобъем множество чисел от 0 до x на два подмножества:

1. Числа от 0 до . Сюда входят все (n + 1) - значные числа, начинающиеся цифрой 0, 1, …, a_n – 1. Сумма их цифр равна dp[0][n + 1] + dp[1][n + 1] + … + dp[a_n – 1][n + 1].

2. Числа от 0 до . Цифра a_n в этих числах встречается ( + 1) раз. Сумма остальных цифр этого множества равна f().

Таким образом

f(x) = + a_n * ( + 1) + f()

Функция info(x, *len, *FirstDigit, *Rest) по входному значению x возвращает количество знаков в числе len, первую цифру числа FirstDigit и число Rest, полученное зачеркиванием первой цифры в числе x.

рекурсивное решение

Рассмотрим рекурсивную реализацию функции f(x). Суммирование цифр чисел от 0 до x = разобьем на две части:

1. суммирование цифр чисел от 0 до ;

2. суммирование цифр чисел от до ;

Рассмотрим первое множество чисел. На последней позиции повторяется последовательность из чисел 0, 1, …, 9 x / 10 раз. Сумма цифр от 0 до 9 равна 45, поэтому сумма единиц в числах первого множества равна x / 10 * 45. Сумма цифр, стоящих на других местах, равна 10 * f(x / 10 – 1).

Сумма цифр в числах второго множества состоит из суммы цифр единиц (0 + 1 + … + a₀) и суммы цифр числа = x /10, умноженного на количество чисел во множестве, то есть на (a₀ + 1). Положим temp = a₀ = x % 10. Пусть sum(x) – функция, вычисляющая сумму цифр числа x. Тогда сумма цифр всех чисел второго множества равна

(temp + 1) * sum(x / 10) + temp * (temp + 1) / 2

ПРОГРАММА

#include <stdio.h>

long long dp[10][11];

int digits[10];

void info(int x,int *len,int *FirstDigit,int *Rest)

{

int pow10 = *len = 1; *Rest = 0;

while(x > 9)

{

(*len)++;

*Rest = *Rest + (x % 10) * pow10;

x /= 10; pow10 *= 10;

}

*FirstDigit = x;

}

long long f(int x)

{

int i, len, FirstDigit, Rest;

long long res;

if (x <= 0) return 0;

info(x,&len,&FirstDigit,&Rest);

for(res = i = 0; i < FirstDigit; i++)

res += dp[i][len];

return res + FirstDigit * (Rest + 1) + f(Rest);

}

class SumThemAll

{

public:

long long getSum(int lowerBound, int upperBound)

{

int i, j, k;

for (i = 0; i < 10; i++) dp[i][0] = 0;

for (k = j = 1; j < 11; j++)

{

dp[0][j] = 0;

for (i = 0; i < 10; i++) dp[0][j] += dp[i][j - 1];

for (i = 0; i < 10; i++) dp[i][j] = dp[0][j] + k * i;

k *= 10;

}

return f(upperBound) - f(lowerBound - 1);

}

};

Рекурсивный вариант решения задачи.

#include <stdio.h>

int sum (int x)

{

return (x <= 0) ? 0 : x % 10 + sum(x / 10);

}

long long f(long long x)

{

if (x <= 0) return 0;

long long res = x / 10 * 45;

long long temp = x % 10;

res = res + 10 * f(x / 10 - 1) + (temp + 1) * sum(x / 10) +

temp * (temp + 1) / 2;

return res;

}

class SumThemAll

{

public:

long long getSum(int lowerBound, int upperBound)

{

return f(upperBound) - f(lowerBound - 1);

}

};